Quantum-Classical Complexity-Security Tradeoff In Secure Multi-Party Computation

摘要

I construct a secure multi-party scheme to compute a classical function by asuccinct use of a specially designed fault-tolerant random polynomial quantumerror correction code. This scheme is secure provided that (asymptotically)strictly greater than five-sixths of the players are honest. Moreover, thesecurity of this scheme follows directly from the theory of quantum errorcorrecting code, and hence is valid without any computational assumption. Ialso discuss the quantum-classical complexity-security tradeoff in securemulti-party computation schemes and argue why a full-blown quantum code isnecessary in my scheme.